//链表 - 合并k个升序链表
//方法一: 创建小根堆
class Solution {
public:
    struct cmp
    {
        bool operator()(const ListNode* n1, const ListNode* n2)
        {
            return n1->val > n2->val;
        } 
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for(auto x : lists)
            if(x) heap.push(x);
        
        ListNode* newHead = new ListNode(0), *cur = newHead;
        while(heap.size())
        {
            auto top = heap.top(); 
            heap.pop();
            cur->next = top;
            cur = cur->next;
            if(top->next) heap.push(top->next);
        }
        cur = newHead->next;
        delete newHead;
        return cur;
    }
};


//方法二: 分治-递归
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        ListNode* newHead = new ListNode(0), *tail = newHead;
        ListNode* cur1 = l1, *cur2 = l2;
        while(cur1 && cur2)
        {
            if(cur1->val <= cur2->val)
            {
                tail = tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail = tail->next = cur2;
                cur2 = cur2->next;
            }
        }
        if(cur1) tail->next = cur1;
        if(cur2) tail->next = cur2;
        return newHead->next;
    }

    ListNode* merge_sort(vector<ListNode*>& lists, int left, int right)
    {
        if(left > right) return nullptr;
        if(left == right) return lists[left];
        int mid = (left + right) >> 1;
        ListNode* l1 = merge_sort(lists, left, mid);
        ListNode* l2 = merge_sort(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) 
    { 
        return merge_sort(lists, 0, lists.size() - 1);    
    }
};
